#!/usr/bin/env python

# Interpreter for the Simple LISP Dialect for Teaching
#
# Author:   Mike Murphy <mamurph@cs.clemson.edu>
# Revision: 10 January 2009
#
# Copyright 2008-2009 Clemson University
#
# Permission is hereby granted, free of charge, to any person obtaining a
# copy of this software and associated documentation files (the "Software"),
# to deal in the Software without restriction, including without limitation
# the rights to use, copy, modify, merge, publish, distribute, sublicense,
# and/or sell copies of the Software, and to permit persons to whom the
# Software is furnished to do so, subject to the following conditions:
#
# The above copyright notice and this permission notice shall be included in
# all copies or substantial portions of the Software.
#
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
# FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
# IN THE SOFTWARE.
#
# This material is based upon work supported under a National Science
# Foundation Graduate Research Fellowship. Any opinions, findings,
# conclusions or recommendations expressed in this publication are those of
# the author(s) and do not necessarily reflect the views of the National
# Science Foundation.

import sys
from parser import Parser
from symbol_table import SymbolTable
from shared_config import CompilerException, PRELOADED_SYMBOLS, SCAN_TYPES
from type_checker import TypeChecker

# Control debugging and trace messages *for this module only*
DEBUG=False
TRACE=False


# Debugging and trace routines
def dbg(msg):
   if DEBUG:
      print >> sys.stderr, '*I:DEBUG*:', msg
#

def trace(msg):
   if TRACE:
      print >> sys.stderr, '*I:TRACE*:', msg
#


# A custom exception for errors that are detected by the interpreter
class InterpreterException(CompilerException):
   def __init__(self, message, line):
      CompilerException.__init__(self, 'Interpreter Error: ' + self.message, \
                                 line)
#


# NOTE: This interpreter deliberately simulates a stack machine.
class Interpreter(object):
   def __init__(self, filename, fh, interactive = False):
      self.filename = filename
      self.fh = fh
      self.interactive = interactive
      self.stack = []     # need an actual stack, not a model
      self.line = 0
      self.symbol_table = SymbolTable(PRELOADED_SYMBOLS)
      #
      self.parser = Parser(self.fh)
      self.type_checker = TypeChecker(self.parser, self.symbol_table)
      #
      self.oper_map = { ('+',  1) : self.unary_plus,
                        ('+',  2) : self.binary_plus,
                        ('-',  1) : self.unary_minus,
                        ('-',  2) : self.binary_minus,
                        ('*',  2) : self.binary_mult,
                        ('/',  2) : self.binary_div,
                        ('%',  2) : self.binary_mod,
                        ('<',  2) : self.binary_lt,
                        ('<=', 2) : self.binary_le,
                        ('>',  2) : self.binary_gt,
                        ('>=', 2) : self.binary_ge,
                        ('=',  2) : self.binary_eq,
                        ('!=', 2) : self.binary_ne,
                        ('!',  1) : self.unary_not,
                        # "if" is a special case
                      }
   #
   def implicit_print(self):
      '''Handles the implicit top-level statement print in SLDT'''
      trace('enter implicit_print')
      print self.stack.pop()
      trace('leave implicit_print')
   def push_terminal(self, token):
      '''Pushes a terminal (int or constant) onto the stack'''
      if token[0] == SCAN_TYPES['INT']:
         self.stack.append(token[1])
      else:
         self.stack.append(self.symbol_table[token[1]])
      self.line = token[2]
   def push_bool(self, value):
      '''Pushes a boolean onto the stack'''
      if value:
         self.stack.append(self.symbol_table['TRUE'])
      else:
         self.stack.append(self.symbol_table['FALSE'])
   #
   def unary_plus(self):
      trace('unary plus: no-op')
   def binary_plus(self):
      trace('enter binary_plus')
      addend1 = self.stack.pop()
      addend2 = self.stack.pop()
      self.stack.append(addend1 + addend2)
      trace('leave binary_plus')
   def unary_minus(self):
      trace('enter unary_minus')
      val = self.stack.pop()
      self.stack.append(-1 * val)
      trace('leave unary_minus')
   def binary_minus(self):
      trace('enter binary_minus')
      # Order needs to be left to right
      right = self.stack.pop()
      left = self.stack.pop()
      self.stack.append(left - right)
      trace('leave binary_minus')
   def binary_mult(self):
      trace('enter binary_mult')
      x1 = self.stack.pop()
      x2 = self.stack.pop()
      self.stack.append(x1 * x2)
      trace('leave binary_mult')
   def binary_div(self):
      trace('enter binary_div')
      denom = self.stack.pop()
      numer = self.stack.pop()
      self.stack.append(numer / denom)
      trace('leave binary_div')
   def binary_mod(self):
      trace('enter binary_mod')
      denom = self.stack.pop()
      numer = self.stack.pop()
      self.stack.append(numer % denom)
      trace('leave binary_mod')
   def binary_lt(self):
      trace('enter binary_lt')
      right = self.stack.pop()
      left = self.stack.pop()
      self.push_bool(left < right)
      trace('leave binary_lt')
   def binary_le(self):
      trace('enter binary_le')
      right = self.stack.pop()
      left = self.stack.pop()
      self.push_bool(left <= right)
      trace('leave binary_le')
   def binary_gt(self):
      trace('enter binary_gt')
      right = self.stack.pop()
      left = self.stack.pop()
      self.push_bool(left > right)
      trace('leave binary_gt')
   def binary_ge(self):
      trace('enter binary_ge')
      right = self.stack.pop()
      left = self.stack.pop()
      self.push_bool(left >= right)
      trace('leave binary_ge')
   def binary_eq(self):
      trace('enter binary_eq')
      right = self.stack.pop()
      left = self.stack.pop()
      self.push_bool(left == right)
      trace('leave binary_eq')
   def binary_ne(self):
      trace('enter binary_ne')
      right = self.stack.pop()
      left = self.stack.pop()
      self.push_bool(left != right)
      trace('leave binary_ne')
   def unary_not(self):
      trace('enter unary_not')
      # NOTE: !x is equivalent to (x == 0) (see code_generator comments)
      self.stack.append(0)
      self.binary_eq()
      trace('leave unary_not')
   #
   def trinary_if(self, condition, then_tree, else_tree):
      trace('enter trinary_if')
      self.handle_subtree(condition)
      trace('stack: ' + str(self.stack))
      tos = self.stack.pop()
      if tos != 0:
         trace('following "then" branch')
         self.handle_subtree(then_tree)
      else:
         trace('following "else" branch')
         self.handle_subtree(else_tree)
      trace('leave trinary_if')
   #
   #
   def handle_subtree(self, subtree):
      trace('enter handle_subtree')
      dbg('subtree: ' + str(subtree))
      if isinstance(subtree, list):
         self.handle_statement(subtree)
      elif isinstance(subtree, tuple):
         self.push_terminal(subtree)
      else:
         trace('leave handle_subtree by exception')
         raise Exception('BUG: handle_subtree got non-list and non-tuple')
      trace('leave handle_subtree')
   def handle_statement(self, statement):
      trace('enter handle_statement')
      dbg('statement: ' + str(statement))
      optoken = statement[0]
      args = statement[1:]
      operator = optoken[1]
      self.line = optoken[2]
      argct = len(args)
      trace('operator: %s  argument count: %d' % (operator, argct))
      if operator != 'if':
         # Stack machine is postfix, so need to handle args first
         for arg in args:
            self.handle_subtree(arg)
         trace('stack (before): ' + str(self.stack))
         dbg('lookup tuple: ' + str((operator, argct)))
         # Check for underflow:
         if argct > len(self.stack):
            raise InterpreterException('stack underflow', self.line)
         self.oper_map[(operator, argct)]()
         trace('stack (after): ' + str(self.stack))
      else:
         # "if" is a special case: need to evaluate the first argument
         self.trinary_if(*args)
      trace('leave handle_statement')
   def run(self):
      trace('enter run')
      eof = False
      code = 0
      while not eof:
         try:
            tree, eof = self.type_checker.check()
            if tree != []:
               for statement in tree:
                  self.handle_statement(statement)
                  self.implicit_print()
         except CompilerException, e:
            if e.line > 0:
               print >> sys.stderr, self.filename + ':' + str(e.line) + ': ' + \
                                    e.message
            else:
               print >> sys.stderr, self.filename + ': ' + e.message
            code = 4
            if self.interactive:
               # Reset the interpreter and type-checker if interactive
               print 'Fatal error encountered: resetting interpreter'
               print 'Use CTRL+D (CTRL+Z on Windows) to exit'
               print ''
               self.stack = []
               self.type_checker = TypeChecker(self.parser, self.symbol_table)
      #
      if self.interactive:
         print 'Maximum stack size at type-checker (since last reset): %d' % \
                self.type_checker.getStackLimit()
      trace('leave run')
      return code
#


if __name__ == '__main__':
   inst = None
   if len(sys.argv) > 1:
      filename = sys.argv[1]
      fh = open(filename, 'r')
      inst = Interpreter(filename, fh, False)
   else:
      print ('*' * 79)
      print (' ' * 23) + 'Simple LISP Dialect for Teaching'
      print ('*' * 79)
      print 'Interpreting code in Interactive Mode. Type CTRL+D (CTRL+Z on' + \
            ' Windows) to exit\n'
      inst = Interpreter('<stdin>', sys.stdin, True)
   code = inst.run()
   sys.exit(code)
#
